package AVL;

import java.util.ArrayList;

import bst.BST;
import bst.BST.TreeNode;

public class AVLTree<E extends Comparable<E>> extends BST<E> {

	public AVLTree() {
	    
	}
	
	
	
	public AVLTree(E[] objects) {
		super(objects);
	}
	
	protected AVLTreeNode<E> createNewNode(E e){
		
		return new AVLTreeNode<E>(e);
	}
	
	public boolean insert(E e) {
		boolean reasult=super.insert(e);
		if(!reasult)
			return false;
		else
			balancePath(e);
		
		return true;
	}
	private void updateHeight(AVLTreeNode<E> node) {
		
		if(node.left==null&&node.right==null) {
			node.height=0;
		}
		else if(node.left==null) {
			node.height=1+((AVLTreeNode<E>)(node.right)).height;
		}
		else if(node.right==null) {
			node.height=1+((AVLTreeNode<E>)(node.left)).height;
		}
		else
			node.height=1+Math.max(((AVLTreeNode<E>)(node.left)).height, ((AVLTreeNode<E>)(node.right)).height);
	}
	
	
	private void balancePath(E e) {
		
		ArrayList<TreeNode<E>> path=path(e);
		
		for(int i=path.size()-1;i>=0;i--) {
			AVLTreeNode<E> A = (AVLTreeNode<E>) path.get(i);
			updateHeight(A);
			AVLTreeNode<E> parentOfA=(A==root)?null:(AVLTreeNode<E>)path.get(i-1);
			
			switch(balanceFactor(A)) {
			
			case -2:if(balanceFactor((AVLTreeNode<E>) A.left)<=0)
				
				   balanceLL(A,parentOfA);
			else
				   balanceLR(A,parentOfA);
			break;
			
			case +2:
				if(balanceFactor((AVLTreeNode<E>) A.left)>=0)
					
					   balanceRR(A,parentOfA);
				else
					   balanceRL(A,parentOfA);
				
			
			
			}
			
			
			
			
			
		}
		
		
		
		
	}
	
	
	private int balanceFactor(AVLTreeNode<E> node) {
		
		if(node.right==null)
			return -node.height;
		if(node.left==null)
			return +node.height;
		else
			return ((AVLTreeNode<E>)(node.right)).height-((AVLTreeNode<E>)(node.left)).height;
		
		
		
		
	}
	
	
	private void balanceLL(TreeNode<E> A,TreeNode<E>parentOfA) {
		
		TreeNode<E> B=A.left;
		
		if(A==root) {
			root=B;
		}
		else {
			if(parentOfA.left==A)
				parentOfA.left=B;
			else
				parentOfA.right=B;
		}
		
		A.left=B.right;
		B.right=A;
		
		updateHeight((AVLTreeNode<E>) A);
		updateHeight((AVLTreeNode<E>) B);
		
		
		
		
	}
	
private void balanceRR(TreeNode<E> A,TreeNode<E>parentOfA) {
		
		TreeNode<E> B=A.right;
		
		if(A==root) {
			root=B;
		}
		else {
			if(parentOfA.left==A)
				parentOfA.left=B;
			else
				parentOfA.right=B;
		}
		
		A.right=B.left;
		B.left=A;
		
		updateHeight((AVLTreeNode<E>) A);
		updateHeight((AVLTreeNode<E>) B);
		
		
		
		
	}

private void balanceLR(TreeNode<E> A,TreeNode<E>parentOfA) {
	
	TreeNode<E> B=A.left;
	TreeNode<E> C=B.right;
	
	if(A==root) {
		root=C;
	}
	else {
		if(parentOfA.left==A) {
			parentOfA.left=C;
		}
		else
			parentOfA.right=C;
	}
	
	B.right=C.left;
	A.left=C.right;
	C.left=B;
	C.right=A;
	

	updateHeight((AVLTreeNode<E>) A);
	updateHeight((AVLTreeNode<E>) B);
	updateHeight((AVLTreeNode<E>) C);
	
	
	
	
	
	
}

private void balanceRL(TreeNode<E> A,TreeNode<E>parentOfA) {
	
	TreeNode<E> B=A.right;
	TreeNode<E> C=B.left;
	
	if(A==root) {
		root=C;
	}
	else {
		if(parentOfA.left==A) {
			parentOfA.left=C;
		}
		else
			parentOfA.right=C;
	}
	
	B.left=C.right;
	A.right=C.left;
	C.left=A;
	C.right=B;
	

	updateHeight((AVLTreeNode<E>) A);
	updateHeight((AVLTreeNode<E>) B);
	updateHeight((AVLTreeNode<E>) C);
	
	
	
	
	
	
}

    public boolean delete(E e) {
    	
    	TreeNode<E> parent=null;
    	TreeNode<E> current=root;
    	
    	while(current!=null) {
    		if(e.compareTo(current.element)<0) {
    			parent=current;
    			current=current.left;
    		}
    		else if(e.compareTo(current.element)>0)
    		{
    			parent=current;
    			current=current.right;
    		}
    		else 
    			break;
    		
    	}
    	
    	if(current==null)
    		return false;
    	if(current.left==null) {
    		if(parent==null)
    			root=current.right;
    		else {
    			if(e.compareTo(parent.element)<0)
    				parent.left=current.right;
    			else
    				parent.right=current.left;
    			
    			balancePath(parent.element);
    		}
    			
    	
    }
    	else {
    		
    		TreeNode<E> rightsMost=current.left;
			TreeNode<E> parentOfRightMost=current;
			
			while(rightsMost.right!=null) {
				
				parentOfRightMost=rightsMost;
				rightsMost=rightsMost.right;
				
			}
			
			current.element=rightsMost.element;
			if(parentOfRightMost.right==rightsMost)
				parentOfRightMost.right=rightsMost.left;
			else
				parentOfRightMost.left=rightsMost.left;
			
			balancePath(parentOfRightMost.element);
    		
    	}
    	

		size--;
		
		
		return true;
    }
	
	protected static class AVLTreeNode<E extends Comparable<E>> extends BST.TreeNode<E>{
		protected int height=0;
		
		public AVLTreeNode(E e) {
			super(e);
		}
	}

}
